package _17_剑指Offer;

import java.util.Arrays;

public class _10_剑指Offer斐波那契数列 {

    public static void main(String[] args) {

        _10_剑指Offer斐波那契数列 v = new _10_剑指Offer斐波那契数列();

        System.out.println(v.fib2(5));

    }

    // 保存前2个值
    public int fib(int n) {
        if (n < 2) return n;
        final int MOD = 1000000007;
        int first = 0;
        int second = 1;
        while (--n >= 2) {
            second = first + second;
            first = second - first;
            second %= MOD;
        }
        return second;
    }


    // 递归过程，计算上一次保存的值
    public int fib2(int n) {
        int[] dp = new int[101];
        Arrays.fill(dp, -1);
        // 初始化dp数据
        dp[0] = 0;
        dp[1] = 1;
        return fib2(n, dp, 1000000007);
    }

    public int fib2(int n, int[] dp, int mod) {
        if (dp[n] != -1) return dp[n];
        dp[n] = (fib2(n - 1, dp, mod) + fib2(n - 2, dp, mod)) % mod;
        return dp[n];
    }

    // 对于斐波那契数列的递归版本，因为存在太多的子序列重复计算，所以当前n足够大，一定会超时
    public int fib1(int n) {
        if (n <= 1) return n;
        return fib1(n - 2) + fib1(n - 1);
    }

}
